前言

嘿嘿～我們又來啦！延續上次那道 Longest Valid Parentheses 的題目，上次我們用的是堆疊方法來解決這個「括號迷宮」，今天我們換一種更不一樣的方式來看看。

這次要用的是 動態規劃！動態規劃可是解題界的「萬用小幫手」，它可以讓我們在解決這類「最優子結構」的問題時事半功倍。那麼，就讓我們用動態規劃來拆解這個題目，看看怎麼優雅地找到最長有效括號的長度吧！準備好了嗎？Let's go！😊

Day26 X Leetcode：最長有效括號 Longest Valid Parentheses

方法 2：動態規劃

動態規劃是一種自底向上的解題方法，非常適合用來解決這類最優子結構的問題。對於這道題，我們可以透過一個 dp 陣列來追蹤每個位置的最長有效括號子字串長度。

思路解析

1. 定義 dp 陣列：

   • 我們使用一個陣列 dp 來儲存以 s[i] 結尾的最長有效括號子字串的長度。
   • dp[i] 表示當字元 s[i] 是一個 ')' 時，以這個 ')' 結尾的最長有效括號長度。如果 s[i] 是 '('，那麼 dp[i] 為 0，因為沒有可能在 ')' 之後找到匹配的左括號。

2. 如何更新 dp：

   • 當我們遇到一個 ')' 時，我們需要判斷它是否能與之前的 '(' 配對，從而更新 dp[i] 的值。
   • 具體來說，當 s[i] 是 ')' 時，分兩種情況討論：
     • 情況 1：如果 s[i-1] 是 '('，那麼我們找到了形如 ...() 的配對。這時，dp[i] = dp[i - 2] + 2。dp[i - 2] 表示在這之前有效子字串的長度，加上這一對括號的長度 2。
     • 情況 2：如果 s[i-1] 是 ')'，那麼我們需要檢查在 i 的位置前面是否存在一個可以配對的 '('。這個 '(' 的位置是 i - dp[i - 1] - 1。如果這個位置是 '('，那麼 dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2。這表示當前的 ')' 與之前的 '(' 配對，加上這對括號內部的有效長度和之前的有效長度。

3. 初始化與結果：

   • 初始化 dp 陣列為 0，因為最開始每個位置的有效長度都是 0。
   • 遍歷字串更新 dp 陣列的過程中，不斷更新一個變數 maxLength 來記錄最長的有效子字串長度。

實作

function longestValidParentheses(s: string): number {
    const dp: number[] = new Array(s.length).fill(0);
    let maxLength = 0;

    for (let i = 1; i < s.length; i++) {
        if (s[i] === ')') {
            if (s[i - 1] === '(') {
                // 情況 1：遇到形如 '()' 的配對
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] === '(') {
                // 情況 2：遇到形如 '))' 且之前有可配對的 '('
                dp[i] = dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }

            // 更新最大長度
            maxLength = Math.max(maxLength, dp[i]);
        }
    }

    return maxLength;
}

解題心法

1. 動態規劃的優勢：

   • dp 陣列可以記錄每一步的最優解，避免重複計算。通過不斷更新每個位置的 dp 值，我們可以在遍歷一次字串的過程中計算出最長的有效子字串長度。

2. 考慮不同的情況：

   • 當我們遇到 ')' 時，我們需要仔細考慮它是否能與前面的括號配對。這樣，我們就可以將問題分成兩種情況進行處理，每種情況都能有效更新 dp 陣列的值。

3. 時間與空間複雜度：

   • 時間複雜度：O(n)，因為我們只需遍歷字串一次。
   • 空間複雜度：O(n)，需要一個 dp 陣列來記錄每個位置的長度。

方法比較（與堆疊法相比）

• 堆疊法：

  • 時間複雜度：O(n)，掃描一次字串。
  • 空間複雜度：O(n)，因為需要堆疊存儲索引。
  • 優點：實作簡單，對於初學者容易理解。
  • 缺點：需要額外的堆疊空間。

• 動態規劃法：

  • 時間複雜度：O(n)，因為我們只需遍歷一次字串並更新 dp。
  • 空間複雜度：O(n)，需要 dp 陣列來儲存每個位置的結果。
  • 優點：可以在遍歷的過程中逐步更新最長長度，思路清晰。
  • 缺點：需要額外的 dp 陣列，對空間的要求與堆疊法類似。

下一步，明天我們會詳細介紹方法 3：雙指針法，然後比較這三種方法的優劣和適用場景！希望這篇對你有幫助，我們明天見吧！😊